from typing import List


class Solution:
    def dfs(self, n, x, y):

        if  not 0 <= x < len(self.board) or not 0 <= y < len(self.board[0]) or self.word[n]!=self.board[x][y]:
            # print(self.board[x][y] ,wordd[n])
            return False

        if n == len(self.word)-1:
            return True
        self.board[x][y]=''
        res= self.dfs(n + 1, x - 1, y) or self.dfs(n + 1, x + 1, y) or self.dfs(n + 1, x, y - 1) or self.dfs(n + 1, x,
                                                                                                          y + 1)
        self.board[x][y]=word[n]
        return res
    def exist(self, board: List[List[str]], word: str) -> bool:
        self.board = board
        self.word = word
        for i in range(len(board)):
            for j in range(len(board[i])):
                if self.dfs(0, i, j): return True
        return False


if __name__ == '__main__':
    s = Solution()
    board =[["a","a"]]

    word = "aaa"
    ans = s.exist(board, word)
    print(ans)
